package com.hy;

import java.util.LinkedList;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:无重复字符的最长子串
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 *
 * 示例 1:
 * 输入: s = "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 *
 * 示例 2:
 * 输入: s = "bbbbb"
 * 输出: 1
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 *
 * 示例 3:
 * 输入: s = "pwwkew"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 *      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 *
 * User:Mr.Du
 * Date:2023/9/21
 * Time:13:43
 */
public class LengthOfLongestSubstring {

    /**
     * 垃圾做法，下面三种做法整体思路就是遇到重复值，那么就让s指向重复值的下一个元素
     * @param ss
     * @return
     */
    public int lengthOfLongestSubstring1(String ss) {
        LinkedList<Character> list = new LinkedList<>();
        int s = 0, f = 0, res = 0;
        while(f < ss.length()){
            if(!list.contains(ss.charAt(f))){
                list.add(ss.charAt(f));
                f++;
            }else{
                res = Math.max(res, f - s);
                list.removeFirst();
                s++;
            }
        }
        return Math.max(res, f - s);
    }

    /**
     * 申请一个255的数组，
     * 不重复就加1
     * 重复就让慢指针指向重复值的下一个不重复的元素，这里的重复值下标是从0开始计算的，并且，清除[0,s]的值，
     * 找出ss.charAt(s) == ss.charAt(f)  最终让s -> s + 1
     * @param ss
     * @return
     */
    public int lengthOfLongestSubstring3(String ss) {
        int s = 0, f = 0, res = 0;
        int[] arr = new int[255];
        while(f < ss.length()){
            if(arr[ss.charAt(f)] == 0){
                arr[ss.charAt(f)]++;
            }else{
                res = Math.max(res, f - s);
                while(ss.charAt(s) != ss.charAt(f)){
                    arr[ss.charAt(s)]--;
                    s++;
                }
                s++;
            }
            f++;
        }
        return Math.max(res, f - s);
    }

    /**
     * 对上面的做法进行优化
     * @param ss
     * @return
     */
    public int lengthOfLongestSubstring(String ss) {
        int s = 0, f = 0, res = 0;
        int[] arr = new int[255];
        while(f < ss.length()){
            arr[ss.charAt(f)]++;
            /**
             * 让s重新指向重复元素的下一个不重复
             */
            while(arr[ss.charAt(f)] > 1){
                arr[ss.charAt(s)]--;
                s++;
            }
            f++;
            res = Math.max(res , f - s);
        }
        return res;
    }


    public static void main(String[] args) {
        LengthOfLongestSubstring los = new LengthOfLongestSubstring();
        int res = los.lengthOfLongestSubstring("tmmzuxt");
        System.out.println(res);
    }
}
